// https://leetcode-cn.com/problems/combinations/
// 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。不能重复

// 最小的开始数=1 最大的开始数=n-k+1
#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

class Solution {
public:
	// 多组合问题用回溯的方式是最好的
    vector<vector<int>> combine(int n, int k) {
		vector<vector<int>> res;
		vector<int> tmp;
		selfCombine(k, 1, n- k + 2, tmp, res);
		return res; // 记这里的一个问题，就是这里没有返回，导致主函数中会报错，terminate called after throwing an instance of 'std::bad_alloc'， 原因是访问内存不存在
    }
	
	// 递归
	void selfCombine(int height, int start, int end, vector<int> tmp, vector<vector<int>> & res){
		if(height == 0){
			res.push_back(tmp);
			return;
		}
		
		for(int i = start; i < end; i++){
			tmp.push_back(i);
			selfCombine(height-1, i+1, end+1, tmp, res);
			tmp.pop_back(); // 回溯
		}
	}
	
	// 二进制
	/*
	0011 3 2+1
	0101 5 4+1
	0110 6 4+2
	1001 9 8+1
	
	
	1010 10 8+2
	
	1100 12 8+4
	*/
	// 这种方法速度太慢了，内存消耗极大
	vector<vector<int>> combine1(int n, int k) {
		vector<vector<int>> res;
		int min = (1 << k) - 1 ; // 注意这里有括号
		int max = (min << (n-k)) + 1;
		cout << min << " " << max << endl;
        if(min >= max){
			vector<int> tmp;
			for(int i = 0; i < n; i++){ // 对比二位数的每一位
				tmp.push_back(i+1);
			}
			res.push_back(tmp);
			return res;
		}
		for(int j = min; j < max; j++){
			bitset<20> bi(j);
			vector<int> tmp;
            int size = 0;
			for(int i = 0; i < n; i++){ // 对比二位数的每一位
				if(bi[i] == 1){
					tmp.push_back(i+1);
                    size++;
				}
			}
			if(size == k){
				res.push_back(tmp);
			}
		}
		
		return res; // 记这里的一个问题，就是这里没有返回，导致主函数中会报错，terminate called after throwing an instance of 'std::bad_alloc'， 原因是访问内存不存在
    }
	
};

int main(){
	Solution so;
	int n = 4;
	int k = 2;
	auto res = so.combine1(n, k);
	
	for(auto item : res){
		for(auto i : item){
			cout << i << ",";
		}
		cout << endl;
	}
	
	return 1;
}